Home | | Latest | About | Random
# 06b Further understanding: Solving system of linear equations in different fields.
Let us consider the linear system $$
\left\{
\begin{array}{}
x & + & y & + & z & = & 1 \\
x & & & + & z & = & 0
\end{array}
\right.
$$ If we are to solve it over the reals, meaning using scalars that are from $\mathbb{R}$, then we proceed as we have been. Let us write out its augmented matrix and perform elementary row operations until it is in echelon form: $$
\begin{array}{}
x \ \ \ y \ \ \ z \ \ \ \ \ \ \ \ \ \ \ \\
\begin{bmatrix}
1 & 1 & 1 & \vdots & 1 \\
1 & 0 & 1 & \vdots & 0
\end{bmatrix} & \stackrel{\text{row}}\sim &
\begin{bmatrix}
\colorbox{lightblue}1 & 1 & 1 & \vdots & 1 \\
0 & \colorbox{lightblue}{$-1$} & 0 & \vdots & -1
\end{bmatrix}
\end{array}
$$ where we see that $z$ is a free variable, with $x,y$ pivot variables. This gives $z$ free, $y=1$, and $x=1-y-z=-z$. Hence $$
x=-z,\ \ y=1, \ \ z=\text{free}.
$$And if our choice of scalars are the reals, $z$ being free means it can be any real numbers. This means there are **infinitely many solutions**, since there are infinitely many choices of real numbers for $z$!
Now let us suppose instead this linear system is meant to be solved only over $\mathbb{Z} / 2 \mathbb{Z} = \{0,1\}$, using the rules introduced in the last section. What changed? Several things: Since $-1=1 \pmod2$, we get instead just $$
x=z, \ \ \ y = 1, \ \ \ z = \text{free}.
$$Further, since $\mathbb{Z} / 2\mathbb{Z} = \{0,1\}$ has only 2 elements, this means $z$ can be one of two choices. So all together there are only two solutions total to this linear system! Namely $(x,y,z)=(0,1,0)$ (when $z=0$) and $(x,y,z)=(1,1,1)$ (when $z=1$).
So **depending on the field of scalars, if there is a free variable it's not "always infinitely many solutions"** -- if the field of scalars is the reals or complex that has infinitely many numbers, then having free variables would lead to infinitely many solutions; if the field of scalars is finite, like $\mathbb{Z} / 2\mathbb{Z}$, then the number of solutions is some finite number, depending on the size of the field!
Just to see another example. Say you we have a linear system and we obtained the following echelon form: $$
\begin{array}{}
x\ \ \ y \ \ \ z \ \ \ \ \ \ \ \ \ \ \ \\
\begin{bmatrix}
\colorbox{lightblue}1 & 1 & 1 & \vdots & 1 \\
0 & 0 & 0 & \vdots & 0
\end{bmatrix}
\end{array}
$$where we have two free variables. Then we have $$
x = 1-y-z, \ \ y=\text{free}, \ \ z = \text{free}.
$$ So how many solutions are there?
- If our field is $\mathbb{R}$ or $\mathbb{C}$, then we have infinitely many solutions.
- If our field is $\mathbb{Z} / 2\mathbb{Z} =\{0,1\}$, then we have a total of $4$ solutions (we can let $y$ be one of $0$ or $1$, and let $z$ be one of $0$ or $1$)
- If our field is $\mathbb{Z} / 3\mathbb{Z} = \{0,1,2\}$, then we have a total of $9$ solutions (we can let $y$ be one of $0,1,2$, and let $z$ be one of $0,1,2$).
- If our field is $\mathbb{Z} / 13 \mathbb{Z} = \{0,1,2,3,4,5,6,7,8,9,10,11,12\}$, then we have a total of $13\times 13 = 169$ many solutions!
So bottom line -- it depends on the field. Most of our discuss will be restricted in $\mathbb{R}$ or $\mathbb{C}$ in this class, however. But finite fields certainly are useful in many places.
By the way, in our very first example here, we performed elementary row operations that did not use any division. Let us see what if we need to divide.
Let us use $\mathbb{Z} / 3\mathbb{Z} = \{0,1,2\}$ as our example with addition and multiplication table below:$$
\begin{array}{c|ccc}
+ & 0 & 1 & 2 \\ \hline
0 & 0 & 1 & 2 \\
1 & 1 & 2 & 0 \\
2 & 2 & 0 & 1
\end{array}\qquad
\begin{array}{c|ccc}
\cdot & 0 & 1 & 2 \\ \hline
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 \\
2 & 0 & 2 & 1
\end{array}
$$from our last section. The multiplication table part is also tell us how to divide. So look for everything that multiplies to $1$. We have $1 \cdot 1 = 1 \pmod 3$ and $2\cdot 2=1 \pmod 3$. So $1/2 = 2 \pmod{3}$.
Ok, now let us solve this linear system over the field $\mathbb{Z} / 3\mathbb{Z}$ : $$
\left\{
\begin{array}{}
2x & + & y & + & 2z & = & 1 \\
x & + & 2y & + & z & = & 2 \\
2x & & & + & z & = & 1
\end{array}
\right.
$$ Ok, let us apply elementary row operations, over $\mathbb{Z} / 3\mathbb{Z}$ on its augmented matrix: $$
\begin{array}{}
& x \ \ \ y \ \ \ z\ \ \quad\quad \\
& \begin{bmatrix}
2 & 1 & 2 & \vdots & 1 \\
1 & 2 & 1 & \vdots & 2 \\
2 & 0 & 1 & \vdots & 2
\end{bmatrix} & \underset{(R_{1})\to2(R_{1})}{\overset{\text{row}}{\sim}} & \begin{bmatrix}
1 & 2 & 1 & \vdots & 2 \\
1 & 2 & 1 & \vdots & 2 \\
2 & 0 & 1 & \vdots & 2
\end{bmatrix} \\
\underset{(R_{2})\to (R_{2})-(R_{1})}{\overset{\text{row}}{\sim}} & \begin{bmatrix}
1 & 2 & 1 & \vdots & 2 \\
0 & 0 & 0 & \vdots & 0 \\
2 & 0 & 1 & \vdots & 2
\end{bmatrix} & \underset{(R_{3})\to (R_{3})+(R_{1})}{\overset{\text{row}}{\sim}} & \begin{bmatrix}
1 & 2 & 1 & \vdots & 2 \\
0 & 0 & 0 & \vdots & 0 \\
0 & 2 & 2 & \vdots & 1
\end{bmatrix} \\
\underset{(R_{2})\leftrightarrow (R_{1})}{\overset{\text{row}}{\sim}} & \begin{bmatrix}
\colorbox{lightblue}1 & 2 & 1 & \vdots & 2 \\
0 & \colorbox{lightblue}2 & 2 & \vdots & 1 \\
0 & 0 & 0 & \vdots & 0
\end{bmatrix}
\end{array}
$$ So this shows that $z$ is a free variable, with $x,y$ pivot variables. Solving pivot variables in terms of the free one, we have $z=\text{free}$, $2y+2z=1$, or $$
2y=1-2z
$$But how do we divide by 2 in $\mathbb{Z} / 3\mathbb{Z}$ ? That's right, multiply by 2! So we have $$
y = 2 - 4z
$$And since $-4=2\pmod 3$, we have $y=2+2z$.
And we have $2x=2-2y-z=2-2(2+2z)-z=2-4-4z-z=-2-5z=1+z \pmod 3$.
Hence the solution to this linear system over the field $\mathbb{Z} / 3\mathbb{Z}$ is $$
x = 1+z, \ \ y = 2+2z, \ \ z = \text{free over } \mathbb{Z} / 3\mathbb{Z}.
$$This gives a total of three solutions, $z$ can take on one of three numbers, $0,1,2$ from $\mathbb{Z} / 3\mathbb{Z}$.
If you have a grasp on this, then I am super proud of you! If this is still iffy, it's ok, just work with real numbers or complex numbers for now.